package stackAndQueue

type Heap struct {
	arr       []int
	isMaxHeap bool
}

// 计算序列长度
func (h Heap) Len() int {
	return len(h.arr)
}

// h.arr[i] < h.arr[j]表示小根堆，h.arr[i] > h.arr[j]表示大根堆
func (h Heap) Less(i, j int) bool {
	if !h.isMaxHeap {
		// 使表达式为true的i所对应元素排前面，j所对应元素排后面；否则i所对应元素排后，j所对应元素排前
		return h.arr[i] < h.arr[j]
	} else {
		return h.arr[i] > h.arr[j]
	}
}

// 交换元素
func (h Heap) Swap(i, j int) {
	h.arr[i], h.arr[j] = h.arr[j], h.arr[i]
}

// 不要直接调用h.Push和Pop方法，而是调用heap.Push()和heap.Pop()
// heap.Push()和heap.Pop()内部会调用h.Push()和h.Pop()进行元素的添加和删除
// 然后再调用up(Push)或down(Pop)对重新调整顺序
func (h *Heap) Push(x interface{}) {
	(*h).arr = append((*h).arr, x.(int))
}

// 删除元素
func (h *Heap) Pop() interface{} {
	n := len(h.arr) - 1
	x := h.arr[n]
	h.arr = h.arr[:n]
	return x
}